package com.da.javatest.algorithm;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @author chenlida
 * @date 2019/4/10 11:34
 * @description
 */
public class BFSDFS {
    public static void main(String[] args) {
        BFSDFS instance = new BFSDFS();
        TreeNode2 tree = instance.bulidTree();
        instance.levelOrderTraversal(tree);
        System.out.println();
        instance.depthTraversal(tree);
    }

    public void levelOrderTraversal(TreeNode2 node) {
        if (node == null) {
            System.out.print("empty tree");
            return;
        }
        Queue<TreeNode2> deque = new ArrayDeque<>();
        deque.add(node);
        while (!deque.isEmpty()) {
            TreeNode2 rnode = deque.remove();
            System.out.print(rnode.val + " ");
            if (rnode.left != null) {
                deque.add(rnode.left);
            }
            if (rnode.right != null) {
                deque.add(rnode.right);
            }
        }
    }

    public void depthTraversal(TreeNode2 node) {
        if (node == null) {
            System.out.print("empty tree");
            return;
        }
        Stack<TreeNode2> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode2 rnode = stack.pop();
            System.out.print(rnode.val + " ");
            if (rnode.right != null) {
                stack.push(rnode.right);
            }
            if (rnode.left != null) {
                stack.push(rnode.left);
            }
        }
    }

    public TreeNode2 bulidTree() {
        TreeNode2 root = new TreeNode2(1);
        TreeNode2 t1 = new TreeNode2(2);
        TreeNode2 t2 = new TreeNode2(3);
        root.left = t1;
        root.right = t2;

        TreeNode2 t3 = new TreeNode2(4);
        TreeNode2 t4 = new TreeNode2(5);
        t1.left = t3;
        t1.right = t4;
        TreeNode2 t5 = new TreeNode2(6);
        TreeNode2 t6 = new TreeNode2(7);
        t2.left = t5;
        t2.right = t6;
        return root;
    }
}
